//
// Created by bleedingfight on 2020/6/29.
//
#include "rebuildTree.h"
TreeNode* rebuildTree(std::vector<int>&preorderNums,std::vector<int>&inorderNums,int startPreorder,int endPreorder,int startInorder,int endInorder){
    int rootValue = preorderNums[startPreorder];
    TreeNode* root = new TreeNode(rootValue);


    if(startInorder == endInorder){
        // 如果中序已经遍历到最后一个元素，而且最后这个元素和前序的元素相同则递归结束
        if(startInorder == endInorder && preorderNums[startPreorder]==inorderNums[startInorder])
            return root;
    }
    // 找到中序序列的根节点位置
    int inorder_index = startInorder;
    for(;inorder_index<inorderNums.size()-1;inorder_index++){
        if(inorderNums[inorder_index] == rootValue)
            break;
    }
    int leftTreeLength = inorder_index-startInorder;
    int leftTreerEnd = leftTreeLength+startPreorder;
    if(leftTreeLength>0){
        //递归构建左子树
        root->left = rebuildTree(preorderNums,inorderNums,startPreorder+1,leftTreerEnd,startInorder,inorder_index-1);
    }
    if(leftTreeLength<endPreorder-startInorder){
        //递归构建右子树
        root->right = rebuildTree(preorderNums,inorderNums,leftTreerEnd+1,endPreorder,inorder_index+1,endInorder);
    }
    return root;


}
